请从字符串中找出一个最长的不包含重复字符的子字符串,计算该最长子字符串的长度。
数据范围:
"abcabcbb"
3
因为无重复字符的最长子串是"abc",所以其长度为 3。
"bbbbb"
1
因为无重复字符的最长子串是"b",所以其长度为 1。
"pwwkew"
3
因为无重复字符的最长子串是 "wke",所以其长度为 3。 请注意,你的答案必须是子串的长度,"pwke" 是一个子序列,不是子串。
class Solution: # 滑动窗口 + 哈希表 def lengthOfLongestSubstring(self , s: str) -> int: mp = {} res = 0 # 设置窗口左边界 left = 0 for right in range(len(s)): if s[right] in mp: mp[s[right]] += 1 else: mp[s[right]] = 1 # 窗口中有重复 while mp[s[right]] > 1: mp[s[left]] -= 1 left += 1 # 维护子串长度最大值 res = max(res, right - left + 1) return res
class Solution: # 双指针(时间换空间) def lengthOfLongestSubstring(self , s: str) -> int: cnt = 1 l = 0 r = 1 while l < len(s) -1 and r < len(s): if s[r] not in s[l:r]: cnt = max(cnt, len(s[l:r+1])) r += 1 else: l += 1 r = l + 1 return cnt
class Solution: def lengthOfLongestSubstring(self , s: str) -> int: # write code here if s==" ": return 1 def cut_s(s,target): s=list(s) ind=s.index(target) s=s[ind+1:]+[target] return ''.join(s) res=[] string='' for i in s: if i not in string: string+=i else: res.append(len(string)) string=cut_s(string, i) res.append(len(string)) return max(res)
class Solution: def lengthOfLongestSubstring(self, s: str) -> int: # write code here maxm, tmp, start = 0, 0, 0 dic = dict() if len(s) <= 1: return len(s) for i in range(len(s)): if s[i] not in dic: dic[s[i]] = i tmp += 1 else: if dic[s[i]] > start: start = dic[s[i]] tmp = i - start dic[s[i]] = i if maxm < tmp: maxm = tmp return maxm
n = len(s) for i in range(n, 0, -1): for j in range(0, n-i+1): if len(s[j:j+i]) == len(set(s[j:j+i])): return len(s[j:j+i])参考排行思路:多使用list的append
a = [] b, c = 0, 0 for i in s: if i not in a: a.append(i) b += 1 else: c = max(c, b) ind = a.index(i) a = a[(ind+1):] a.append(i) # !!!! b = len(a) return max(b ,c)
class Solution: def lengthOfLongestSubstring(self, s) -> int: if not str: return 0 # tmp代表以第i-1个元素结尾的子串最大长度 tmp, res = 1, 1 # 记录每个字符最新出现的下标 index = {s[0]: 0} for i in range(1, len(s)): if s[i] in index: tmp = tmp + 1 if i - index[s[i]] > tmp else (i - index[s[i]]) else: tmp += 1 index[s[i]] = i res = max(tmp, res) return res